You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example

Input: 1 -> 2 -> 3 -> 4
Output: 1 -> 4 -> 2 -> 3

Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 5 -> 2 -> 4 -> 3

Step

1. 先建立快慢指針找到 linked list 的中間點

  // find the middle
  let fast = head;
  let slow = head;
  while (fast.next?.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

2. 將 linked list 由剛剛找的的中間 node 分為兩個 linked list 並將右邊的 linked list 反轉
   

3. 將左邊的 linked list 和右邊的 linked list 合併
   

Coding

/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
*/
var reorderList = function (head) {
  // find the middle
  let fast = head;
  let slow = head;
  while (fast.next?.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // reverse
  let curr = slow.next;
  slow.next = null;
  let prev = null;
  while (curr) {
    let tmp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = tmp;
  }

  let h1 = head;
  let h2 = prev;

  while (h2) {
    let tmp = h1.next; 
    h1.next = h2;
    h1 = h2;
    h2 = tmp;
  }
};

Time complexity: O(n)